#ifndef BASE_PATHFINDING_ALGORITHM_HPP
#define BASE_PATHFINDING_ALGORITHM_HPP

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <unordered_map>
#include <vector>

#include <SFML/System/Vector2.hpp>

#include <SmegTools/Config.h>
#include <SmegTools/Pattern/Pool.hpp>

#include "../Node.hpp"

#ifdef _DEBUG
namespace sf {
    class Font;
    class Text;
    class RenderWindow;
}
#endif

#include <SmegTools/Debug/DebugNew.hpp>

namespace smeg {
    namespace ai {
        class Grid;

////////////////////////////////////////////////////////////
/// Base class for Pathfinding algorithm
////////////////////////////////////////////////////////////
class BasePathfindingAlgorithm
{
public:
    ////////////////////////////////////////////////////////////
    /// Constructor/Destructor
    ////////////////////////////////////////////////////////////
                                BasePathfindingAlgorithm( Grid* _pGrid );
    virtual                     ~BasePathfindingAlgorithm();

    ////////////////////////////////////////////////////////////
    /// Find a path between start and end
    ///
    /// \param _Start : Start point 
    /// \param _End :   End point 
    ///
    ////////////////////////////////////////////////////////////
    virtual const std::vector< sf::Vector2f >& FindPath( const sf::Vector2f& _Start, const sf::Vector2f& _End ) = 0;

    ////////////////////////////////////////////////////////////
    /// Clear last found path infos
    ///
    ////////////////////////////////////////////////////////////
    void                        ClearPath();

    /*********************** Accessors ************************/
    const std::vector< sf::Vector2f >& GetLastPath() const;

protected:
    typedef std::vector< Node* >                td_PathPriorityQueue;
    typedef std::unordered_map< int, Node* >    td_PathMap;

    ////////////////////////////////////////////////////////////
    /// Constructor
    ////////////////////////////////////////////////////////////
                                BasePathfindingAlgorithm();

    ////////////////////////////////////////////////////////////
    /// Reconstruct a path from the given node to its farthest parent
    ///
    /// \param _pLastNode :     Node to reconstruct the path from
    ///    
    ////////////////////////////////////////////////////////////
    void                        ReconstructPath( Node* _pLastNode );

    ////////////////////////////////////////////////////////////
    /// Heuristic function to compute the F value of a Node
    ///
    /// \param _Point :         Point from where we go
    /// \param _End :           Point where we want to go
    ///
    /// \return The distance between _Point and _End (depends on the heuristic used)
    ///    
    ////////////////////////////////////////////////////////////
    float                       Heuristic( const sf::Vector2i& _Point, const sf::Vector2i& _End );

    /********************* Static members *********************/
    static smeg::tools::Pool< Node > s_PoolNode;
    static sf::Vector2u         s_Sides[8];

    /******************* Protected members ********************/
    Grid*                       m_pGrid;
    
    td_PathPriorityQueue        m_OpenSet;
    td_PathMap                  m_ClosedMap;
    td_PathMap                  m_DoneNodes;

    std::vector< sf::Vector2f > m_LastFoundPath;

#ifdef _DEBUG
    sf::Font*                   DEBUG_Font;
    sf::Text*                   DEBUG_Text;
public:
    virtual bool                DebugStartPath( const sf::Vector2f& _Start, const sf::Vector2f& _End ) = 0;
    virtual bool                DebugStepPath( const sf::Vector2f& _Start, const sf::Vector2f& _End ) = 0;
    virtual void                DebugRenderFindPath( sf::RenderWindow* _pRenderWindow );
#endif
};

/************************ Inline **************************/
inline const std::vector< sf::Vector2f >& BasePathfindingAlgorithm::GetLastPath() const {
    return m_LastFoundPath;
}

    } // namespace ai
} // namespace smeg

#include <SmegTools/Debug/DebugNewOff.hpp>

#endif // BASE_PATHFINDING_ALGORITHM_HPP
